package Datastruct.Kruskal;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

//贪心算法
public class Greedy {
    public static void main(String[] args) {
        //创建一个集合，存储城市

        ArrayList<String> arealist = new ArrayList<>();
        arealist.add("北京");
        arealist.add("上海");
        arealist.add("天津");
        arealist.add("广州");
        arealist.add("深圳");
        arealist.add("成都");
        arealist.add("杭州");
        arealist.add("大连");

        HashSet<String> area1 = new HashSet<>();
        area1.add("北京");
        area1.add("上海");
        area1.add("天津");

        HashSet<String> area2 = new HashSet<>();
        area2.add("北京");
        area2.add("广州");
        area2.add("深圳");

        HashSet<String> area3 = new HashSet<>();
        area3.add("成都");
        area3.add("上海");
        area3.add("杭州");

        HashSet<String> area4 = new HashSet<>();
        area4.add("上海");
        area4.add("天津");

        HashSet<String> area5 = new HashSet<>();
        area5.add("杭州");
        area5.add("大连");

        //电台覆盖城市的范围
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        broadcasts.put("k1", area1);
        broadcasts.put("k2", area2);
        broadcasts.put("k3", area3);
        broadcasts.put("k4", area4);
        broadcasts.put("k5", area5);

        //用yu存储符合的电台
        ArrayList<String> keylist = new ArrayList<>();
        //用于存储每次遍历时，交集最多的电台
        String key = null;
        //临时存储电台所覆盖的城市
        HashSet<String> teamp = new HashSet<>();
        //循环的条件是arealist没有城市数据，说明每个城市都被覆盖
        while (!arealist.isEmpty()) {
            for (String broadcastkey : broadcasts.keySet()) {
                //先进行清空
                teamp.clear();
                teamp.addAll(broadcasts.get(broadcastkey));
                //retainall  取交集
                teamp.retainAll(arealist);
                if (teamp.size() > 0 && (key == null || teamp.size() > broadcasts.get(key).size())) {
                    key = broadcastkey;
                }
            }
            if (key != null) {
                keylist.add(key);
                arealist.removeAll(broadcasts.get(key));
                key = null;
            }
        }


        System.out.println(keylist.toString());


    }
}
